Array, vector & map
*******************


Array
=====


Rôle
----

Un `std::array <https://en.cppreference.com/w/cpp/container/array>`_ contient un nombre fixe d'éléments de même type.
 
Pourquoi utiliser un std::array plutôt qu'un tableau (int T[10]) :

	* Les arrays sont des objets, ils peuvent donc être passés par copie ou par référence.
	* La fonction membre *at(i)* permet de vérifier la validité de l'indice avant d'accéder au i-ème élément.
	* Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche...

Pour instancier un *array*, vous devez :

	* Ecrire une directive *#include <array>* en début de programme
	* En l'absence de : *using namespace std*, vous devez écrire *std::array*
	 

Présentation rapide
-------------------

.. csv-table:: Opérations sur les arrays
        :header: "Type", "Exemple", ""
        :widths: 10, 10, 20
		

	 
		Initialisation, "array<int, 3> a = {1, 2, 3};", 
		Initialisation, "array<int, 3> a {1, 2, 3};", 
		Initialisation, "array<int, 3> a({1, 2, 3});", 
		Initialisation, "array<int, 3> a = {};", Avec initialisation des valeurs : les numériques sont mis à zéro !
		Initialisation, "array<int, 3> a;", Sans initialisation
		Méthode,		"a.fill(value)", Initialise tous les éléments à la valeur donnée
		Méthode,		"a.at(i)", Retourne une référence vers le i-ème élément AVEC bound-checking
		Méthode,		"a[i]", Retourne une référence vers le i-ème élément SANS bound-checking
		Méthode,		a.size(), Retourne le nombre d'éléments
		Méthode,		a.swap(b), Permute les éléments des deux arrays
		

Quizzz
======

.. quiz:: Arrayaa
	:title: Array
		

	*	:quiz:`{"type":"TF","answer":"F"}` La fonction *length* retourne le nombre d'éléments.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe *at(i)* ou *[i]* sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La syntaxe : *array<int, 3> a {1, 2, 3};* est valide.
	*	:quiz:`{"type":"TF","answer":"T"}` Il est possible d'instancier un array sans initialiser ses valeurs.
	*	:quiz:`{"type":"FB","answer":"fill"}`  Quel est le nom de la fonction initialisant l'ensemble des éléments à une valeur donnée.


Vector
======

Rôle
----


Un `std::vector <https://en.cppreference.com/w/cpp/container/vector>`_ représente une liste de **taille dynamique** d'éléments de même type.


Pourquoi utiliser un *std::vector* :

	* Classe modèle pouvant s'adapter à tout type.
	* Les vectors sont des objets, ils peuvent donc être passés par copie ou par référence.
	* Pas de limite de taille.
	* Les algorithmes de la STL peuvent être appliqués sur ces objets : tri, recherche...	 
	* La fonction membre *at(i)* permet de vérifier la validité de l'indice avant d'accéder au i-ème élément
	* Gestion automatisée de la mémoire : allocation, libération.

	
	

Présentation rapide
-------------------

Pour instancier un objet vector, vous devez :

	* Mettre une directive *#include <vector>*  en début de programme
	* En l'absence de : *using namespace std*, vous devez écrire std::array


.. csv-table:: Opérations sur les vectors
        :header: "Type", "Exemple", ""
        :widths: 10, 10, 20
	 
		Initialisation, "vector<int> L;", Vector vide ; pas d'éléments dans la liste
		Initialisation, "vector<int> L = {};", Idem
		Initialisation, "vector<int> L = {1,2,3,4};",
		Initialisation, "vector<int>  L( {1,2,3,4} )", 
		Initialisation, "vector<int> L( );", Confusion => Déclaration d'une fonction retournant un vector
		Initialisation, "vector<int> v1(10);", Taille fixée à 10 éléments + INITIALISATION à zéro
		Initialisation, "vector<int> v1(10,5);", Taille fixée à 10 éléments initialisés à la valeur 5
		Initialisation, "vector<int> v2(v1);", Initialisation par copie
		Méthode,	"L.at(i)", Retourne une référence vers le i-ème élément AVEC bound-checking
		Méthode,	"L[i]", Retourne une référence vers le i-ème élément SANS bound-checking
		Méthode,	L.size(), Retourne le nombre d'éléments
		Méthode,    L.empty(), Indique si la liste est vide
		Méthode,	L.clear(), Retire et détruit tous les éléments de la liste
		Méthode,	L.resize(n), Force le nombre d'éléments à *n* 
		Méthode,	L.push_back(v),  Insère une copie de l'élément *v* en fin de liste 
		Méthode,    L.pop_back(),   Retire et détruit le dernier élément de la liste
		Méthode, 	L.back(), Retourne une référence vers le dernier élément de la liste
		Méthode,    L.erase(iter), Supprime l'élément désigné par l'itérateur *iter*
		Méthode,	"L.insert(iter,v)", Insère une copie de l'élément *v* à la position désignée par l'itérateur *iter*

		
	

 
.. warning:: Tous les éléments dans une liste de type *vector* sont de même type. Ainsi, si vous stockez un *double* dans une liste de type *vector<int>*, alors il sera implicitement converti en entier.

La fonction **resize(n)** fixe le nombre d'éléments :

	* Si *n < size()* alors les derniers éléments sont détruits.
	* Si *n = size()* aucun effet.
	* Si *n > size()* il y a création de nouveaux éléments par appel au constructeur par défaut. 



.. note:: Certaines méthodes des vectors portent des noms similaires ce qui prête à confusion. On pense ici aux fonctions membres *resize()* et *reserve()* ainsi que *size()* et *capacity()*. Une clarification s'impose ! Un objet *vector* alloue une zone mémoire servant de buffer. La mécanique interne du *vector* fait en sorte que la taille de ce buffer soit supérieure au nombre d'éléments stockés. La méthode **reserve()** permet de fixer la taille de ce buffer et **capacity()** retourne sa taille. Par exemple, si vous savez que 10 000 000 d'éléments vont être stockés, alors, il peut être utile de fixer directement la taille du buffer à cette grandeur ce qui évite de multiples redimensionnements et permet de gagner en efficacité. Ainsi, Ces deux fonctions permettent une optimisation fine des objets *vector*.  	


Quizzz
======

.. quiz:: vectorrr
	:title: Vector
		

	*	:quiz:`{"type":"TF","answer":"F"}` La fonction *pop_back* insère un élément en fin.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe *at(i)* ou *[i]* sont identiques en tout point.
	*	:quiz:`{"type":"TF","answer":"T"}` La fonction *size* retourne le nombre d'éléments.
	*	:quiz:`{"type":"TF","answer":"F"}` La syntaxe : *vector<int> v(10);* crée une liste et initialise ses éléments à la valeur 10.
	*	:quiz:`{"type":"FB","answer":"fill"}`  Quel est le nom de la fonction initialisant l'ensemble des éléments à une valeur donnée ?
	*	:quiz:`{"type":"FB","answer":"clear"}`  Quel est le nom de la fonction retirant tous les éléments ?
	*	:quiz:`{"type":"FB","answer":"empty"}`  Quel est le nom de la fonction indiquant si la liste est vide ?
	*	:quiz:`{"type":"FB","answer":"resize"}`  Quel est le nom de la fonction permettant de fixer le nombre d'éléments dans la liste.
	

Map
===

 

Un `std::map <https://en.cppreference.com/w/cpp/container/map>`_ représente un dictionnaire permettant d'associer une valeur (value) à une clé (key) pouvant être un entier comme un string !
	
.. note:: Si les dictionnaires sont si souples et si pratiques, pourquoi ne pas utiliser que des dictionnaires ? Oui cette question peut être posée ! En fait ils sont plus souples, mais chaque opération sur un dictionnaire est plus longue que sur un *vector*, il y a donc un surcoût à cette souplesse.

Présentation rapide
-------------------

.. csv-table:: Opérations sur les maps
        :header: "Type", "Exemple", ""
        :widths: 10, 10, 20
		

	 
		Initialisation, "map<string,int> m = { {\""one\"",1}, {\""two\"",2} };",  
		Affectation, m[\"trois\"] = 3; ,Associe la valeur 3 à la clé \"trois\"
		Opérateur[], cout << m[\"deux\"] , Retourne la valeur associée à la clé \"deux\"
		Méthode, m.count(key) > 0 , Teste si la clé existe dans ce dictionnaire
		Méthode, m.erase(\"trois\"),  Supprime la paire clé/valeur correspondant à la clé \"trois\"
		Méthode, m.size(), Nombre de paires clé/valeur dans le dictionnaire
		
	


Parcours
========

.. warning:: Les présentations ci-dessous sont valables pour un *array* comme pour un *vector*


En mode read-only
-----------------

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 3> a = {1, 2, 3};
		for (int v : a)  std::cout << v << " ";
		for (int v : a)  v = 4;	 // attention v est une variable locale
		for (int v : a)  std::cout << v << " ";
	}
	
	>> 1 2 3
	>> 1 2 3
	
En mode read-write
------------------

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 3> a = {1, 2, 3};
		for (int v  : a)  std::cout << v << " ";
		for (int &v : a)  v = 4;  // cette fois v est une référence
		for (int v  : a)  std::cout << v << " ";
	}
	
	>> 1 2 3
	>> 4 4 4

.. warning:: Un *vector* ne peut gérer le retrait ou l'ajout d'élément durant un parcours. 

Map
---

Pour les dictionnaires, il y a une légère différence car la boucle *for* retourne un objet dont :

   * La variable *first* correspond à la clé
   * La variable *second* correspond à la valeur

.. code-block:: cpp

	#include <iostream>
	#include <map>
	using namespace std;

	int main() 
	{
		map<string,int> myMap = {{"one",1}, {"two",2}, {"three",3}};

		for ( auto couple : myMap) 
			cout << couple.first << " => " << couple.second << endl;
	}

	>> one => 1
	>> three => 3
	>> two => 2


Les itérateurs
==============

Présentation
------------


.. warning:: Les présentations ci-dessous sont valables pour un *array* comme pour un *vector*


La norme de la STL n'impose aucun choix d'implémentation. Elle décrit juste les fonctions membres et éventuellement impose leur complexité : *temps constant*, *logarithmique* ou *linéaire amortie*. Ainsi, les containers de la STL peuvent aussi bien utiliser en interne des indices ou des adresses pour classer leurs données. De plus, il ne faut pas oublier qu'il existe plusieurs implémentations de la STL qui peuvent entraîner des choix d'implémentation différents :


* **libstdc++** : fournie avec GCC et utilisée pour sa large compatibilité avec différentes architectures.
* **LLVM libc++** : fournie avec Clang et conçue pour être légère.
* **Microsoft STL** : fournie avec Microsoft Visual Studio et optimisée pour les systèmes Windows.
* STL personnalisée : certaines entreprises créent leurs propres versions ou modifications de la STL pour répondre à des besoins spécifiques.

Il a donc fallu choisir une abstraction pour fournir une syntaxe indépendante de l'implémentation choisie pour le container.
L'abstraction mise en place s'appelle un **itérateur** (iterator). Ce choix est judicieux, mais la syntaxe des itérateurs peut parfois donner des cheveux blancs. On aime ou on aime pas, mais, c'est le choix de la STL et on doit savoir travailler avec.



Les itérateurs remplacent ainsi les indices, il faut éviter d'utiliser la valeur 0 ou le paramètre *size()* :

   * begin() : retourne un itérateur positionné sur le premier élément.
   * end() : retourne un itérateur positionné a fin du container : un élément fictif placé après le dernier élément.
   * \*it : avec *it* un itérateur ; retourne une référence vers l'élément désigné par cet itérateur.
   


.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 5> arr = {1, 2, 3, 4, 5};
		
		std::cout << *arr.begin() << std::endl;   // affiche le premier élément
		*arr.begin() = 9;                         // modifie le premier élément
		for(int v : arr) std::cout << v << " ";   // affiche la liste
	}  
	
	>> 1
	>> 9 2 3 4 5 
	
.. note:: Un itérateur permet un accès en lecture/écriture. Pour un accès en mode read-only, le langage fournit des const iterator ainsi que les méthodes  *cbegin()* et *cend()*.


	
Le mot-clef auto
----------------


Le type des itérateurs est assez long à écrire : *array<T, N>::iterator*, pour cela, 
on préfère utiliser le mot-clef **auto** qui force le langage a déduire automatiquement le type.

.. code-block:: cpp

	#include <iostream>
	#include <array>

	int main()
	{
		std::array<int, 5> arr = {1, 2, 3, 4, 5};
		auto it = arr.begin();
	}
   
   

Exemple avec les vectors
------------------------

Il existe une arithmétique sur les itérateur. Ainsi l'expression *begin()+1* désigne un itérateur associé au deuxième élément de la liste.
Voici quelques exemples :


.. code-block:: cpp

 	#include <iostream>
	#include <vector>
	using namespace std;

	int main()
	{
		vector<int>  L = {2,3,4};
		for (int v : L) cout << v << endl;
		
		L.erase(L.begin()+1);  // supprimme le 2ième élément
		for (int v : L) cout << v << endl;
		
		L.insert(L.begin()+1,8); // insére 8 à la deuxième place
		for (int v : L) cout << v << endl;
	}
	>> 2 3 4
	>> 2 4 			// L.erase(L.begin()+1);
	>> 2 8 4		// L.insert(L.begin()+1,8);

 
 
   
Les algorithmes 
===============

.. warning:: Les présentations ci-dessous sont valables pour un *array* comme pour un *vector*

Exemples
--------

Voici quelques exemples des algorithmes fournis dans la STL :

.. code-block:: cpp

	#include <iostream>
	#include <algorithm>
	#include <array>
	using namespace std;

	int main()
	{
		array<int, 10> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

		// FIND
		auto it = find(arr.begin(), arr.end(),9);
		*it = 0;
		for (int v : arr) cout << v << " ";
		cout << endl;
		
		// SORT
		sort(arr.begin(), arr.end());
		for (int v : arr) cout << v << " "; 
		cout << endl; 
		
		// REVERSE
		reverse(arr.begin(), arr.end());
		for (int v : arr) cout << v << " "; 
		cout << endl;
	}
	
	>> 3 1 4 1 5 0 2 6 5 3  FIND
	>> 0 1 1 2 3 3 4 5 5 6  SORT
	>> 6 5 5 4 3 3 2 1 1 0  REVERSE
	   


.. note:: Un effort de simplification a été fait dans ce cours relativement aux syntaxes présentées pour les itérateurs. Cependant, lorsque vous trouverez des informations sur internet, certains auteurs pourront fournir un code beaucoup plus difficile à lire, il faut le savoir.